ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpc/billing-tables/test.py

   1 #!/usr/bin/python
   2 import random
   3 import os
   4
   5 MAXLEN = 4
   6
   7 def ranp(n):
   8   return ''.join([random.choice('0123456789') for i in range(n)])
   9
  10 def ranincr(n):
  11   return random.randint(0, 10**(n / 2))
  12
  13 def rango(n):
  14   while True:
  15     s1 = ranp(n)
  16     s2 = str(int(s1) + ranincr(n))
  17     if len(s2) != len(s1): continue
  18     i = 0
  19     while i < len(s1) and s1[i] == s2[i]:
  20       i += 1
  21     while i > 0 and random.choice([0, 1, 1, 1]) == 0:
  22       i -= 1
  23     s1, s2 = s1[:i] + s1[i:], s2[i:]
  24     if s2 == '':
  25       return s1, s1
  26     else:
  27       return s1, s2
  28
  29 def plan():
  30   return random.choice(['nenuco', 'roque', 'moniche', 'mifus', 'invalid'])
  31
  32 def gentabla():
  33   tabla = []
  34   for i in range(random.randint(1, 20)):
  35     s1, s2 = rango(random.randint(1, MAXLEN))
  36     p = plan()
  37     tabla.append((s1, s2, p))
  38   return tabla
  39
  40 def pad(num, P='0'):
  41   return num + (10 - len(num)) * P
  42
  43 def genstrs(l):
  44   if l == 0:
  45     yield ''
  46     return
  47   for r in genstrs(l - 1):
  48     for dig in range(10):
  49       yield r + str(dig)
  50
  51 def enumerar(fr, to, pref):
  52   pot = 1
  53   while fr + pot <= to:
  54     while fr + pot <= to and fr % (pot * 10) != 0:
  55       yield decor(fr / pot, pref)
  56       fr += pot
  57     pot *= 10
  58     pref -= 1
  59   while fr + pot > to:
  60     pot /= 10
  61     pref += 1
  62   while pot > 0: # and fr + pot <= to:
  63     while fr + pot <= to and to % (pot * 10) != 0:
  64       yield decor(fr / pot, pref)
  65       fr += pot
  66     pot /= 10
  67     pref += 1
  68
  69 def readtabla(a):
  70   f = file(a, 'r')
  71   ls = f.readlines()
  72   tabla = []
  73   for x in map(lambda l: l.strip(' \t\r\n').split(' '), ls[1:]):
  74     tabla.append((x[0], x[2], x[3]))
  75   f.close()
  76   return tabla
  77
  78 def decor(x, k):
  79   if k == 0:
  80     #return '...'
  81     return ''
  82   else:
  83     xx = str(x)
  84     assert len(xx) <= k
  85     return (k - len(xx)) * '0' + xx #+ '...'
  86
  87 def resultado_referencia1(tabla):
  88   #tabla = tabla[::-1]
  89   tabla1 = []
  90   for start, end, plan in tabla:
  91     tabla1.append((pad(start), pad(start[:-len(end)] + end, '9'), plan))
  92   tabla = tabla1
  93
  94   tabla2 = {}
  95   def cuanto_da(n):
  96     n = pad(n)
  97     if n in tabla2:
  98       return tabla2[n]
  99     for start, end, plan in tabla:
 100       if start <= n and n <= end:
 101         tabla2[n] = plan
 102         return plan
 103     tabla2[n] = 'invalid'
 104     return 'invalid'
 105
 106   for n in genstrs(MAXLEN):
 107     cdn = cuanto_da(n)
 108     #print n, cdn
 109     yield n, cdn
 110
 111 def resultado_referencia(tabla):
 112   res = []
 113   l = list(resultado_referencia1(tabla))
 114   l.append((int(l[-1][0]) + 1, 'invalid'))
 115   i0 = None
 116   v0 = None
 117   for i, v in l:
 118     if v != v0:
 119       if v0 not in [None, 'invalid']:
 120         ###print int(i0), int(i), v0
 121         for j in enumerar(int(i0), int(i), len(i0)):
 122           res.append((j, v0))
 123       v0 = v
 124       i0 = i
 125   g = file('tmp.referencia', 'w')
 126   g.write('%i\n' % (len(res),))
 127   for x, y in res:
 128     g.write('%s %s\n' % (x, y,))
 129   g.close()
 130   return res
 131
 132 def resultado_implementacion(tabla):
 133   f = file('tmp.in', 'w')
 134   f.write('%i\n' % (len(tabla),))
 135   for start, end, plan in tabla:
 136     f.write('%s - %s %s\n' % (start, end, plan))
 137   f.close()
 138   os.system('cat tmp.in | ./main > tmp.implementacion')
 139   f = file('tmp.implementacion', 'r')
 140   ls = map(lambda x: tuple(x.strip(' \t\r\n').split(' ')), f.readlines()[1:])
 141   f.close()
 142   return ls
 143
 144 def main():
 145   tabla = gentabla()
 146   #tabla = readtabla('tmp.in')
 147   ###print tabla
 148   l1 = resultado_referencia(tabla)
 149   l2 = resultado_implementacion(tabla)
 150   print l1
 151   print l2
 152   if l1 != l2:
 153     print 'falla'
 154     assert False
 155
 156 while True:
 157   main()
 158